package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Decode1734
 * @description: 给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。
 *
 * 它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。
 *
 * 给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/decode-xored-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/5/1111:21
 * @since V1.0
 */
public class Decode1734 {

    public int[] decode(int[] encoded) {
        //先求出res[0]-->res[n-2]的异或，不包括res[n-1]
        int a=encoded[0];
        for (int i=2;i<encoded.length;i=i+2){
            a = a^encoded[i];
        }
        //因为res[]中包含前n个正整数的排列
        int b = 1;
        for (int i=2;i<=encoded.length+1;i++){
            b = b^i;
        }
        //a为res[0,n-2]的异或，b为res[0,n-1]的异或，求出res[n-1]
        int c = a^b;
        int[] res = new int[encoded.length + 1];
        res[res.length-1] = c;
        for (int i=res.length-2;i>=0;i--){
            res[i] = res[i+1] ^ encoded[i];
        }
        return res;
    }
}
